第 382 场力扣周赛

给定操作次数内使剩余元素的或值最小

题目

输入长度为 \(n\) 的整数数组 \(nums\) 和整数 \(k\)，输出执行至多 \(k\) 次操作之后，将数组中所有剩余元素按位或的最小值。每次操作可以选择一个下标 \(i\)，满足 \(0\leq i<n\)，将 \(nums[i]\) 和 \(nums[i+1]\) 替换为它们按位与的结果。注意，是两个数替换为一个数。

数据范围：\(1\leq n\leq 10^{5}\)，\(0\leq nums[i]<2^{30}\)，\(0\leq k< n\)。

思路

要使按位或的结果最小，肯定是从高位到低位消除。但是高位消除的方式会影响低位消除的方式，它们是相关的，不能单独计算每一位的操作次数。如果暴力枚举所有位的组合，会有 \(2^{30}\) 种情况，肯定会超时。如何计算？其实，只需要考虑从高位到低位的组合方式。从高位开始，能够消除的位总是应该被消除，然后判断加上更低的一位是否能被消除（保留相关性），如果不能，则该低位就永远不会被消除，以此类推。那么如何判断某个位的组合是否能被消除？从前往后遍历数组，贪心的将数组分割为若干按位与结果为 0 的子数组（假设为 \(m\)），则当前组合消除所需的操作次数为 \(n-m\)。具体可以看下灵茶山的题解和小羊的题解。